package leetcode每日一题;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1. 问题描述 (此题是一道非常经典的数据结构的算法体，有许多变形，如求解85.矩阵的最大面积)
 *      给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *      求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 2. 算法分析
 *      1. 暴力法
 *          固定每一个高度，考虑以当前柱子为中心的两边的可延伸的最大宽度
 *
 *      2. 单调栈
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 最大的矩形_矩形图 {
    public static void main(String[] args) {
        // 测试&& 是否存在 短路 的效果
        int[] a = {1,2};
        if (1 < 0 && a[2] == 2) {
            System.out.println("...");
        }
    }

    /**
     * 暴力解法 固定高度，找出符合条件的最大宽度   时间复杂度高O(n^2)
     * @param heights
     * @return
     */
    public int largestRectangleArea1(int[] heights) {
        if(heights.length == 0) {
            return 0;
        }
        if(heights.length == 1) {
            return heights[0];
        }
        int maxarea = 0; // 记录最大面积
        // 扫描柱子的高度
        for(int i = 0; i < heights.length; i++) {
            if(i == 0) {
                int width = 1;
                int right = i+1;
                while(heights[right] >= heights[i] && right < heights.length) {
                    width++;
                    right++;
                    if(right == heights.length) {
                        break;
                    }
                }
                // 退出循环时找到了最大的宽度
                maxarea = Math.max(maxarea,width*heights[i]);
            }
            else if(i == heights.length-1) {
                int width = 1;
                int left = i-1;
                while(heights[left] >= heights[i] && left >= 0) {
                    width++;
                    left--;
                    if(left == -1) {
                        break;
                    }
                }
                // 循环退出找到了最大的宽度
                maxarea = Math.max(maxarea,width*heights[i]);
            }
            else {
                // 中间的柱子
                int width = 1;
                int left = i-1;
                int right = i+1;
                while(heights[left] >= heights[i] && left >= 0) {
                    width++;
                    left--;
                    if(left == -1) {
                        break;
                    }
                }
                while(heights[right] >= heights[i] && right < heights.length) {
                    width++;
                    right++;
                    if(right == heights.length) {
                        break;
                    }
                }
                maxarea = Math.max(maxarea,width*heights[i]);
            }
        }
        return maxarea;
    }

    /**
     * 暴力法，但是对上述代码的优化写法  实际上我们利用&&短路的特性可以不需要在上面分多类讨论
     * 代码的性能并没有什么实质性的提升，只是暴力的代码实现更加简洁了
     * 对于代码中的width变量实际上可以使用left和right指针来表示 width = right-left+1
     * 所以可以省略
     * @param heights
     * @return
     */
    public static int largestRectangleArea2(int[] heights) {
        int len = heights.length;
        if(len == 0) {return 0;}
        if(len == 1) {return heights[0];}
        int maxarea = 0; // 记录最大面积
        for(int i = 0; i < len; i++) {
            int left = i-1; // 左侧指针
            int right = i+1; // 右侧指针
            int width = 1; // 初始化长度为当前柱子的宽度1
            while(left >= 0 && heights[left] >= heights[i]) {
                width++;
                left--;
            }
            while(right < heights.length && heights[right] >= heights[i]) {
                width++;
                right++;
            }
            maxarea = Math.max(maxarea,heights[i]*width);
        }
        return maxarea;
    }


    /**
     * 单调栈实现 (目前还没有看懂!!!!!!!)
     * @param heights
     * @return
     */
    public static int largestRectangleArea3(int[] heights) {

        return -1;
    }

    /**
     *
     * @return
     */
    public static int[] test(int[] heights) {
        int len = heights.length;
        if (len == 0) {return new int[] {};} // 数组为空
        int[] left = new int[len]; // left[i]: 表示的含义第i个柱子的左侧以第i个柱子为尾端的连续最小索引
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            if (stack.peek() <= heights[i]) {
                stack.push(heights[i]); // 如果当前入栈元素大于等于栈顶元素，直接入栈
                // left[i] = i;
            }
            // 如果不走上述的if判断，说明当前的入栈元素小于栈顶元素
            while(!stack.isEmpty() && heights[i] < stack.pop()) {

            }
            // 当循环退出时，将当前元素入栈
            stack.push(heights[i]);
            // left[i] = ?;
        }
        return left;
    }

}
